package 数据结构.链表.带头链表.非循环链表.双向链表;

import 数据结构.链表.IList;
import 数据结构.链表.带头链表.非循环链表.单向链表.MyLinkedList;

public class MyLinkList implements IList {
    static class ListNode{
        private int value;
        private ListNode next;
        private ListNode prev;
        public ListNode(int value){
            this.value = value;
        }
    }
    ListNode Head;
    ListNode Last;
    public MyLinkList(){
        Head = new ListNode(-1);
        Last = Head;
    }

    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        if(Head == Last){
            Head.next = newNode;
            newNode.prev = Head;
            Last = newNode;
        }else{
            newNode.next = Head.next;
            newNode.prev = Head.next.prev;
            Head.next = newNode;
            newNode.next.prev = newNode;
        }

    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(Head == Last){
            Head.next = newNode;
            newNode.prev = Head;
            Last = newNode;
        }else{
            Last.next = newNode;
            newNode.prev = Last;
            Last = newNode;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        if(index<=0 ){
            System.out.println("index不合法  Index="+index);
            return;
        }
        ListNode newNode = new ListNode(data);
        //index 设置为第几个元素的位置
        ListNode cur = Head.next;
        ListNode prev = Head;
        int count = 0;
        while(cur != null){
            count++;
            if(count == index){
                newNode.next = prev.next;
                newNode.prev = cur.prev;
                cur.prev = newNode;
                prev.next = newNode;
                return;
            }
            cur = cur.next;
            prev = prev.next;
        }
        addLast(data);
    }

    @Override
    public boolean contains(int key) {
        if(size() == 0){
            System.out.print("链表为空  ");
            return false;
        }
        ListNode cur = Head.next;
        while(cur != null){
            if(cur.value == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(size() == 0){
            System.out.println("链表为空");
            return;
        }
        ListNode cur = Head.next;
        ListNode prev = Head;
        while(cur != null){
            if(cur.value == key){
                prev.next = cur.next;
                cur.next.prev = prev;
                cur = prev.next;
                System.out.println("删除成功");
                return;
            }
            prev = prev.next;
            cur = cur.next;
        }
        System.out.println("未找到改元素");
    }

    @Override
    public void removeAllKey(int key) {
        if(size() == 0){
            System.out.println("链表为空");
            return;
        }
        ListNode cur = Head.next;
        ListNode prev = Head;
        int count = 0;
        while(cur != null){
            if(cur.value == key){
                if(cur.next == null){
                    prev.next = null;
                    return;
                }else{
                    prev.next = cur.next;
                    cur.next.prev = prev;
                    cur = prev.next;
                    System.out.println("删除成功");
                    count++;
                    continue;
                }
            }
            prev = prev.next;
            cur = cur.next;
        }
        if(count == 0){
            System.out.println("未找到改元素");
        }
    }

    @Override
    public int size() {
        int size = 0;
        ListNode cur = Head.next;
        while(cur != null){
            size++;
            cur = cur.next;
        }
        return size;
    }

    @Override
    public void clear() {
        ListNode cur = Head.next;
        while(cur != null){
            Head.next = cur.next;
            cur = Head.next;
        }
    }

    @Override
    public void display() {
        ListNode cur = Head.next;
        while(cur != null){
            System.out.print(cur.value +" ");
            cur=cur.next;
        }
        System.out.println();
    }
}
